Các công thức khác Nguyên lý bao hàm-loại trừ

Nguyên lý đôi khi được phát biểu dưới dạng sau[10] : nếu

g ( A ) = ∑ S ⊆ A f ( S ) {\displaystyle g(A)=\sum _{S\subseteq A}f(S)}

thì

f ( A ) = ∑ S ⊆ A ( − 1 ) | A | − | S | g ( S ) {\displaystyle f(A)=\sum _{S\subseteq A}(-1)^{|A|-|S|}g(S)}

 

 

 

 

(⁎⁎)

Phiên bản tổ hợp và phiên bản xác suất của nguyên lý bao hàm-loại trừ đều lấy từ (⁎⁎).

Chứng minh

Đặt m _ = { 1 , 2 , … , m } {\displaystyle {\underline {m}}=\{1,2,\ldots ,m\}} , f ( m _ ) = 0 {\displaystyle f({\underline {m}})=0} , và

f ( S ) = | ⋂ i ∈ m _ ∖ S A i ∖ ⋃ i ∈ S A i |  và  f ( S ) = P ( ⋂ i ∈ m _ ∖ S A i ∖ ⋃ i ∈ S A i ) {\displaystyle f(S)=\left|\bigcap _{i\in {\underline {m}}\smallsetminus S}A_{i}\smallsetminus \bigcup _{i\in S}A_{i}\right|{\text{ và }}f(S)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\smallsetminus S}A_{i}\smallsetminus \bigcup _{i\in S}A_{i}\right)}

tương ứng với mọi tập hợp S {\displaystyle S} với S ⊊ m _ {\displaystyle S\subsetneq {\underline {m}}} . Thì ta thu được

g ( A ) = | ⋂ i ∈ m _ ∖ A A i | , g ( m _ ) = | ⋃ i ∈ m _ A i |  và  g ( A ) = P ( ⋂ i ∈ m _ ∖ A A i ) ,     g ( m _ ) = P ( ⋃ i ∈ m _ A i ) {\displaystyle g(A)=\left|\bigcap _{i\in {\underline {m}}\smallsetminus A}A_{i}\right|,\quad g({\underline {m}})=\left|\bigcup _{i\in {\underline {m}}}A_{i}\right|{\text{ và }}g(A)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\smallsetminus A}A_{i}\right),~~g({\underline {m}})=\mathbb {P} \left(\bigcup _{i\in {\underline {m}}}A_{i}\right)}

tương ứng với tất cả tập A {\displaystyle A} thoả mãn A ⊊ m _ {\displaystyle A\subsetneq {\underline {m}}} . Điều này đúng là bởi các phần tử a {\displaystyle a} của ∩ i ∈ m _ ∖ A A i {\displaystyle \cap _{i\in {\underline {m}}\smallsetminus A}A_{i}} có thể nằm trong các A i {\displaystyle A_{i}} khác (các A i {\displaystyle A_{i}} với i ∈ A {\displaystyle i\in A} ), và công thức ∩ ∖ ∪ {\displaystyle \cap \smallsetminus \cup } chạy qua tất cả mở rộng khả thi của các tập hợp { A i ∣ i ∈ m _ ∖ A } {\displaystyle \{A_{i}\mid i\in {\underline {m}}\smallsetminus A\}} cùng với các A i {\displaystyle A_{i}} khác, đếm a {\displaystyle a} chỉ với các tập khớp với điều kiện "là phần tử của" của a {\displaystyle a} , khi S {\displaystyle S} chạy qua tất cả tập con của A {\displaystyle A} (như trong định nghĩa của g ( A ) {\displaystyle g(A)} ).

Bởi f ( m _ ) = 0 {\displaystyle f({\underline {m}})=0} , ta thu được từ (⁎⁎) với A = m _ {\displaystyle A={\underline {m}}} rằng

∑ m _ ⊇ T ⊋ ∅ ( − 1 ) | T | − 1 g ( m _ ∖ T ) = ∑ ∅ ⊆ S ⊊ m _ ( − 1 ) m − | S | − 1 g ( S ) = g ( m _ ) {\displaystyle \sum _{{\underline {m}}\supseteq T\supsetneq \varnothing }(-1)^{|T|-1}g({\underline {m}}\smallsetminus T)=\sum _{\varnothing \subseteq S\subsetneq {\underline {m}}}(-1)^{m-|S|-1}g(S)=g({\underline {m}})}

và sau khi đổi vế, thì sẽ thu được bản tổ hợp và bản xác suất của nguyên lý bao hàm-loại trừ.

Nếu ta coi n {\displaystyle n} là tập các ước nguyên tố của nó, thì (⁎⁎) là dạng tổng quát của công thức biến đổi ngược Möbius cho các số tự nhiên square-free (là các số không chia hết cho bình phương của bất kỳ số nguyên tố nào). Do vậy, (⁎⁎) được xem là công thức biến đổi ngược Möbius cho đại số liên thuộc của tập sắp thứ tự riêng phần tất cả tập con của A.

Đối với dạng tổng quát của bản đầy đủ của công thức biến đổi ngược Möbius, (⁎⁎) phải được tổng quát hoá bằng cách xét các đa tập (cho phép có phần tử trùng nhau trong tập hợp). Khi dùng đa tập thay vì tập hợp, Công thức (⁎⁎) trở trình

f ( A ) = ∑ S ⊆ A μ ( A − S ) g ( S ) {\displaystyle f(A)=\sum _{S\subseteq A}\mu (A-S)g(S)}

 

 

 

 

(⁎⁎⁎)

trong đó A − S {\displaystyle A-S} là đa tập thoả mãn ( A − S ) ⊎ S = A {\displaystyle (A-S)\uplus S=A} , và

  • μ(S) = 1 nếu S là tập hợp (tức đa tập không có cặp phần tử trùng nhau) có số lực lượng chẵn
  • μ(S) = −1 nếu S là tập hợp có số lực lượng lẻ.
  • μ(S) = 0 if S là đa tập (tức S có cặp phần tử trùng nhau).

Quan sát rằng μ ( A − S ) {\displaystyle \mu (A-S)} là ( − 1 ) | A | − | S | {\displaystyle (-1)^{|A|-|S|}} của (⁎⁎) trong trường hợp A − S {\displaystyle A-S} là tập hợp.

Chứng minh (⁎⁎⁎)

Thay

g ( S ) = ∑ T ⊆ S f ( T ) {\displaystyle g(S)=\sum _{T\subseteq S}f(T)}

vào vế phải của (⁎⁎⁎). Để ý rằng f ( A ) {\displaystyle f(A)} xuất hiện một lần ở cả hai bên của ⁎⁎⁎). Do đó ta phải chứng minh với mọi T {\displaystyle T} thoả mãn T ⊊ A {\displaystyle T\subsetneq A} , các phần tử f ( T ) {\displaystyle f(T)} sẽ tự khử nhau trong vế phải của (⁎⁎⁎). Để làm vậy, cố định T {\displaystyle T} sao cho T ⊊ A {\displaystyle T\subsetneq A} và lấy một phần tử a ∈ A {\displaystyle a\in A} bất kỳ sao cho a ∉ T {\displaystyle a\notin T} .

Quan sát rằng A − S {\displaystyle A-S} phải là tập hợp với mỗi xuất hiện dương hay âm của f ( T ) {\displaystyle f(T)} trong phải của (⁎⁎⁎) và được chọn theo đa tập S {\displaystyle S} thoả mãn T ⊆ S ⊆ A {\displaystyle T\subseteq S\subseteq A} . Mỗi lần xuất hiện của f ( T ) {\displaystyle f(T)} trên vế phải (⁎⁎⁎) thu được bằng lấy S {\displaystyle S} sao cho A − S {\displaystyle A-S} là tập hợp chứa phần tử a {\displaystyle a} sẽ triệt tiêu với giá trị thu được bằng lấy tập S {\displaystyle S} tương ứng thoả mãn A − S {\displaystyle A-S} là tập hợp không chứa phần tử a {\displaystyle a} . Từ đây suy ra kết quả cần tìm